package ch05;

//单词查找树
public class TrieST {
    //基数
    private static int R = 128;
    private Node root;


    private static class Node{
        //单词的终点标志，保存了单词字符串
        Object val;
        Node[] next = new Node[R];

    }


    public Node get(String key){
        return get(root,key,0);
    }

    private Node get(Node node,String key,int length){
        if (node == null) {
            return null;
        }
        if (length == key.length()) {
            return node;
        }
        return get(node.next[key.charAt(length)], key, length + 1);


    }

    public void put(String key) {
        root = put(root, key,0);
    }

    private Node put(Node node, String key,int length) {

        if (node == null) {
            node = new Node();
        }
        if (length == key.length()) {
            node.val = key;
            return node;
        }

        node.next[key.charAt(length)]= put(node.next[key.charAt(length)], key, length + 1);
        return node;


    }

    public void selAll(){
        selAll(root);

    }
    //获取所有单词
    private void selAll(Node node){
        for (int i = 0; i < R; i++) {
            Node next = node.next[i];
            if (next !=null) {
                if (next.val != null) {
                    System.out.println(next.val);
                }else{
                    selAll(next);
                }
            }
        }


    }

    //查找最长前缀
    public String longestPrefixOf(String s) {

        int searchLen = search(root, s, 0, 0);
        return s.substring(0, searchLen);

    }

    private int search(Node x, String s, int d, int length) {
        if (x == null) {
            return length;
        }
        if (s.length() == d) {
            return d;
        }

        length= d;

        return search(x.next[s.charAt(d)], s,d + 1, d);

    }

    public void delete(String key){
        root = delete(root, key,0);
    }

    private Node delete(Node node,String key,int length){
        if (node == null) {
            return null;
        }

        if (key.length() == length) {
            node.val=null;
            boolean flag = true;
            //判断删除的该key后是否还有其他节点 比如 要删除 abc 后面还有 abcd
            for (int i = 0; i < R; i++) {
                if (node.next[i] != null) {
                    flag = false;
                }
            }

            return flag ? null : node;
        }
        int c = key.charAt(length);

        node.next[c] = delete(node.next[c], key, length + 1);

        boolean flag = true;


        //判断删除的该key后是否还有其他节点 比如 要删除 abc 后面还有 abcd
        for (int i = 0; i < R; i++) {
            if (node.next[i] != null) {
                flag = false;
            }
        }

        return flag ? null : node;



    }



    public static TrieST getTrieST(){
        TrieST trieST = new TrieST();
        trieST.put("apple");
        trieST.put("banana");
        trieST.put("bananad");
        trieST.put("cake");
        trieST.put("china");
        trieST.put("trump");
        trieST.put("elbert");
        trieST.put("submit");


        return trieST;
    }



    public static void main(String[] args) {
        TrieST trieST = getTrieST();
        Node node = trieST.get("submit");
        System.out.println(node.val);
        System.out.println("------------selAll");
        trieST.selAll();
        System.out.println("------------longestPrefixOf");
        String bananad = trieST.longestPrefixOf("subz");
        System.out.println(bananad);
        System.out.println("-----------------");
        trieST.delete("banana");
        trieST.selAll();
        System.out.println(trieST.get(bananad).val);
    }
}
